import java.util.*;

public class Day1 {
    // 2971、找到最大周长的多边和
    public long largestPerimeter(int[] nums) {
        // 对数组进行排序，之后计算数组的和
        // 因为 求的是a1 + a2 + a3 + ... + ak-1 > ak 那么最长为k
        // 所以我们可以计算所有的和之后从后往前减，来进行比较
        Arrays.sort(nums);
        long sum = 0;
        for(int num : nums) {
            sum += num;
        }

        // 从后往前计算
        for(int i = nums.length - 1;i >= 2;i--){
            int x = nums[i];
            if(sum - x > x){
                return sum;
            }
            sum -= x;
        }
        return -1;
    }


    // 128、最长连续序列
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int len = 0;
        // 把数组中的数都存放到哈希表中，去重
        for(int num : nums) {
            set.add(num);
        }

        // 我们去遍历哈希表而非原数组
        for(int x : set) {
            // 查看x-1是否存在在哈希表中，存在就要跳过这个哈希值，去查找下一个哈希值
            if(set.contains(x-1)){
                continue;
            }
            // 不存在就以x为起点查找x+1之后的数据按照加一的顺序有多少个
            int start = x;
            int count = 0;
            while(set.contains(start)){
                start++;
                count++;
            }
            len = Math.max(len,count);
        }
        return len;
    }


    // 49、字母异位词分组
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for(String str : strs) {
            char[] s = str.toCharArray();
            Arrays.sort(s);
            String key = new String(s);
            List<String> list = map.getOrDefault(key,new ArrayList());
            list.add(str);
            map.put(key,list);
        }
        return new ArrayList(map.values());
    }


    // 2588、统计美丽子数组的数目
    public long beautifulSubarrays(int[] nums) {
        // 这个统计美丽数，就是子数组中的所有数据对应的 二进制位 的1的个数为偶数就是 美丽数组
        // 这里可以使用 前缀和进行解决问题，这里得到 前缀和其实计算的是 异或和
        // 比如 3 1 2
        // 3:011
        // 1:001
        // 2:010
        // 它们 异或和 在一起的话，二进制位置上的偶数的1的个数，会疑惑为0，之后它们 异或在一起就是 0，
        // 所以美丽数组就是统计子数组异或在一起后为0的个数，也就是把求k换成求0

        long ret = 0;
        int sum = 0;
        Map<Integer,Integer> map = new HashMap<>();
        // 处理一下 前缀和正好等于0的情况，这时候，我们的0这个位置就要增加一次
        map.put(0,1);

        for(int x : nums) {
            sum ^= x;
            int cnt = map.getOrDefault(sum - 0,0);
            ret += cnt;
            map.put(sum,map.getOrDefault(sum,0) + 1);
        }
        return ret;
    }


    // 304、二维区域和检索-矩阵不可变
    int[][] dp;
    public void NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        dp = new int[m + 1][n + 1];
        // dp是从[1,1] 开始的存储，那么我们要把有关于 dp的都在原来的基础上加一
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                // 原数组和dp都是从[1,1]开始的公式：
                // dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i][j]
                // 下标要从0开始
                // 原数组从[0,0] dp从[1,1] 的公式：
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + matrix[i][j]; // 有关于dp的统统加1
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        // 原数组和dp都是从[1,1]开始的公式：
        // dp[row2][col2] - dp[row1 - 1][col2] - dp[row2][col1 - 1] + dp[row1 - 1][col1 - 1]
        // 对于使用也是统统加一
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }


    // 303、区域和检索-数组不可变
    private int[] dp1;

    public void NumArray(int[] nums) {
        // 前缀和

        // 原数组是从0开始的，dp1存储的时候是从1下标开始的，dp[0] = 0，是为了处理边界条件
        dp1 = new int[nums.length + 1];
        for(int i = 0;i < nums.length;i++) {
            // 原数组和dp都是从[1,1]开始的公式：
            // dp1[i] = dp1[i - 1] + nums[i]
            // 下标要从0开始
            // 原数组从[0,0] dp1从[1,1] 的公式：
            dp1[i + 1] = dp1[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        // 正常来说，求right到left的前缀和的话，正常来说，应该是dp1[right] - dp1[left - 1],但是这个nums和dp1的开始位置不一样，所以dp1要增加1位
        return dp1[right + 1] - dp1[left];
    }
}
